#include "opp.h"

inline uint8_t rewrite_to_axiom(gr_token token, parsing_ctx *ctx)
{
  uint32_t offset;
  const uint32_t *end, *ptr;

  ptr = ctx->rewrite;
  offset = ptr[token_value(token)];
  ptr = &ptr[offset];
  end = ptr + *ptr + 1;
  for (++ptr; ptr != end; ++ptr) {
    if (*ptr == S) {
      return 1;
    }
  }
  return 0;
}

inline token_node *get_last_terminal(precedence_stack *prec_stack, token_node *c_prev, token_node *current_list_pos, token_node *list_end)
{
  token_node *list_itr = get_precedence_stack_node_at_index(prec_stack, prec_stack->tos - 1);
  token_node *last_terminal = NULL;
  if (prec_stack->tos == 0 || list_itr == NULL) {
    list_itr = c_prev;
  }
  while (list_itr != NULL && list_itr != current_list_pos && list_itr != list_end) {
    if (is_terminal(list_itr->token)) {
      last_terminal = list_itr;
    }
    list_itr = list_itr->next;
  }
  return last_terminal;
}

inline void get_next_token(token_node **current_list_pos, token_node **prev_list_pos, token_node *list_end,
    token_node *c_next, uint8_t *TERMINATOR, const char * const *gr_token_name)
{
  *prev_list_pos = *current_list_pos;
  if ((*current_list_pos)->next == NULL) {
    DEBUG_PRINT("Last token in the string, getting #.\n")
    *current_list_pos = c_next;
    *TERMINATOR = 1;
    return;
  }
  *current_list_pos = (*current_list_pos)->next;
  if (*current_list_pos != list_end) {
    DEBUG_PRINT("Got next token %s.\n", gr_token_name[token_value((*current_list_pos)->token)])
  } else {
    DEBUG_PRINT("Getting c_next %s. End of substring.\n", gr_token_name[token_value(c_next->token)])
    *current_list_pos = c_next;
    *TERMINATOR = 1;
  }
}

inline prec_rel set_precedence(token_node *current_list_pos, precedence_stack *prec_stack,
    token_node *c_prev, token_node *list_end, parsing_ctx *ctx)
{
  prec_rel prec;
  token_node *last_terminal = get_last_terminal(prec_stack, c_prev, current_list_pos, list_end);
  DEBUG_PRINT("Last terminal: %p, %s, current_list_pos: %p, %s\n", 
      last_terminal, ctx->gr_token_name[token_value(last_terminal->token)],
      current_list_pos, ctx->gr_token_name[token_value(current_list_pos->token)])
  prec = PRECEDENCE(ctx->matrix, last_terminal->token, current_list_pos->token);
  if (c_prev->token == TERM && prec == EQ && prec_stack->tos == 0) {
    prec = GT;
  }
  return prec;
}

inline int8_t init_parser(opp_chrono *chrono, uint8_t id,
    opp_result **result, token_node_stack *stack, parsing_ctx *ctx)
{
  /* Initialize variables */
#ifdef CHRONO
  chrono->timer_t = 0;
  chrono->nonterm_timer_t = 0;
  chrono->prec_timer_t = 0;
  chrono->stacking_timer_t = 0;
  chrono->reduction_timer_t = 0;
  chrono->backtrack_timer_t = 0;
  chrono->semantics_timer_t = 0;
  chrono->token_timer_t = 0;
  chrono->badtrack_timer_t = 0;
  chrono->term_timer_t = 0;
#endif

  *result = (opp_result *) malloc(sizeof(opp_result));
  if (*result == NULL) {
    DEBUG_PRINT("ERROR> result = NULL after malloc\n")
    return -1;
  }
  init_token_node_stack(stack, ctx->NODE_ALLOC_SIZE);
  return 0;
}

inline void return_wip(opp_result *result, opp_chrono *chrono,
    token_node *current_list_pos,
    precedence_stack *prec_stack, reduction_list *red_list,
    reduction_list *temp_red_list, token_node_stack *stack, parsing_ctx *ctx)
{
  result->result = 1;
#ifdef TEST
  result->reallocations = stack->reallocations;
  result->max_prec = prec_stack->max;
  result->list_realloc = red_list->reallocations;
  result->list_max = red_list->max;
#endif
  CHRONO_METER(chrono)
  DEBUG_PRINT("current_list_pos %p. Returning.\n", current_list_pos)
  PRINT_TOKEN_NODE_FRONTIER(ctx)
  free_precedence_stack(prec_stack);
  free_reduction_list(red_list);
  free_reduction_list(temp_red_list);
}

inline void return_not_recognized(opp_result *result, opp_chrono *chrono,
    token_node *current_list_pos,
    precedence_stack *prec_stack, reduction_list *red_list,
    reduction_list *temp_red_list, token_node_stack *stack, parsing_ctx *ctx)
{
  result->result = 2;
#ifdef TEST
  result->reallocations = stack->reallocations;
  result->max_prec = prec_stack->max;
  result->list_realloc = red_list->reallocations;
  result->list_max = red_list->max;
#endif
  CHRONO_METER(chrono)
  DEBUG_PRINT("current_list_pos %p. Returning.\n", current_list_pos)
  PRINT_TOKEN_NODE_FRONTIER(ctx)
  free_precedence_stack(prec_stack);
  free_reduction_list(red_list);
  free_reduction_list(temp_red_list);
}

inline void return_error(opp_result *result, opp_chrono *chrono,
    token_node *current_list_pos,
    precedence_stack *prec_stack, reduction_list *red_list,
    reduction_list *temp_red_list, token_node_stack *stack, parsing_ctx *ctx)
{
  DEBUG_PRINT("ERROR> relation precedence undefined on terminal token or next token is NULL. Abort.\n");
  result->result = 3;
#ifdef TEST
  result->reallocations = stack->reallocations;
  result->max_prec = prec_stack->max;
  result->list_realloc = red_list->reallocations;
  result->list_max = red_list->max;
#endif
  CHRONO_METER(chrono)
  DEBUG_PRINT("current_list_pos %p. Returning.\n", current_list_pos)
  PRINT_TOKEN_NODE_FRONTIER(ctx)
  free_precedence_stack(prec_stack);
  free_reduction_list(red_list);
  free_reduction_list(temp_red_list);
}

inline void return_success(opp_result *result, opp_chrono *chrono,
    token_node *current_list_pos,
    precedence_stack *prec_stack, reduction_list *red_list,
    reduction_list *temp_red_list, token_node_stack *stack, parsing_ctx *ctx)
{
  result->result = 0;
#ifdef TEST
  result->reallocations = stack->reallocations;
  result->max_prec = prec_stack->max;
  result->list_realloc = red_list->reallocations;
  result->list_max = red_list->max;
#endif
  CHRONO_TIMER(&chrono->term_timer_s, &chrono->term_timer_e, &chrono->term_timer_t)
  CHRONO_METER(chrono)
  DEBUG_PRINT("Recognition.\ncurrent_list_pos %p. Returning.\n", current_list_pos) 
  PRINT_TOKEN_NODE_FRONTIER(ctx)
  free_precedence_stack(prec_stack);
  free_reduction_list(red_list);
  free_reduction_list(temp_red_list);
}

inline void reduction_step(reduction_list *temp_reduction_list, uint32_t red_list_node, token_node *list_itr, parsing_ctx *ctx)
{
  uint32_t node, offset;
  const uint32_t *itr, *end;
  DEBUG_PRINT("Iterating over position in reduction tree: %d\n", red_list_node)
  if (is_terminal(list_itr->token)) {
    itr = &ctx->gr_token_alloc[token_value(list_itr->token)];
    end = itr + 1;
  } else {
    offset = ctx->rewrite[list_itr->token];
    itr = &ctx->rewrite[offset];
    end = itr + *itr + 1;
    ++itr;
  }
  /* For each token in the current stack element token list. */
  for(; itr != end; ++itr) {
    DEBUG_PRINT("Iterating over stack tokens: %s\n", ctx->gr_token_name[token_value(*itr)])
    node = get_son_with(ctx->reduction_tree, red_list_node, *itr);
    /* If current position has a son corresponding to the current token, navigate the tree. */
    if (node != 0) {
      DEBUG_PRINT("Adding to reduction_list: %d\n", node)
      append_position_on_reduction_list(temp_reduction_list, node);
    }
  }
  DEBUG_PRINT("Finished checking current position.\n")
  DEBUG_PRINT("Printing resulting temp_reduction_list: ")
  PRINT_REDUCTION_LIST(temp_reduction_list)
}

inline void get_next_reduction_token(token_node **list_itr)
{
  DEBUG_PRINT("Getting next reduction element.\n")
  *list_itr = (*list_itr)->next;
  DEBUG_PRINT("Next reduction element: %p\n", *list_itr)
}

inline void perform_rewrite(token_node *rewrite_pos,
    gr_token current, gr_token goal, token_node_stack *stack, parsing_ctx *ctx)
{
  gr_function semantics_fun;
  gr_token next;
  uint32_t node;
  const gr_rule *rule;

  while (current != goal) {
    node = ctx->reduction_tree[0];
    node = get_son_with(ctx->reduction_tree, node, current);
    rule = &ctx->grammar[ctx->reduction_tree[node]];
    semantics_fun = rule->semantics;
    next = rule->lhs;
    DEBUG_PRINT("Performing immediate rewrite reduction %s->%s.\n",
      ctx->gr_token_name[token_value(next)], ctx->gr_token_name[token_value(current)])
    semantics_fun(rewrite_pos, stack, ctx);
    current = next;
  }
}

inline void call_semantics(opp_chrono *chrono, reduction_list *main_reduction_list, 
    precedence_stack *prec_stack, token_node *prev_list_pos, token_node_stack *stack, parsing_ctx *ctx)
{
  gr_function semantics_fun;
  const gr_rule *rule;
  token_node *rewrite_pos;
  uint8_t rhs_itr;

  CHRONO_GETTIME(&chrono->semantics_timer_s)
    /* Manage rewrite rules. */
    rule = &ctx->grammar[ctx->reduction_tree[get_reduction_position_at_index(main_reduction_list, 0)]];
  rewrite_pos = prev_list_pos;
  for (rhs_itr = 0; rhs_itr < rule->rhs_length; ++rhs_itr) {
    /* Detect immediate rewrite token. */
    perform_rewrite(rewrite_pos, rewrite_pos->next->token, rule->rhs[rhs_itr], stack, ctx);
    rewrite_pos = rewrite_pos->next;
  }

  /* Reduce handle. */
  DEBUG_PRINT("Reducing.\n") 
  semantics_fun = rule->semantics;
  DEBUG_PRINT("Calling semantic function with node: %p.\n", prev_list_pos) 
  semantics_fun(prev_list_pos, stack, ctx);
  CHRONO_TIMER(&chrono->semantics_timer_s, &chrono->semantics_timer_e, &chrono->semantics_timer_t)
  DEBUG_PRINT("Called semantic function.\n")
}

opp_result *opp_parse(token_node *c_prev, token_node *c_next, uint8_t id,
    token_node *list_begin, token_node *list_end, parsing_ctx *ctx)
{
  opp_result *result = NULL;
  reduction_list *main_reduction_list, *temp_reduction_list; /* reduction_list represents where we are inside the reduction tree. */
  uint32_t reduction_list_itr;
  token_node *current_list_pos = list_begin, *prev_list_pos = c_prev, *list_itr = NULL;
  uint32_t node = 0;
  precedence_stack prec_stack;
  prec_rel prec;
  uint8_t TERMINATOR = 0, REDUCTION_ERROR = 0;
  token_node_stack stack;

  opp_chrono chrono;
  if (init_parser(&chrono, id, &result, &stack, ctx) != 0) {
    DEBUG_PRINT("ERROR> Could not init parser variables. Aborting.\n");
    result->result = 3;
#ifdef TEST
    result->reallocations = 0;
#endif
    return result;
  }
  DEBUG_PRINT("============================================\n\tOPP parsing started\n============================================\n")
  DEBUG_PRINT("C_prev: %p, %s\n", c_prev, ctx->gr_token_name[token_value(c_prev->token)])
  DEBUG_PRINT("C_next: %p, %s\n", c_next, ctx->gr_token_name[token_value(c_next->token)])
  DEBUG_PRINT("begin: %p, end: %p\n", list_begin, list_end)
  PRINT_TOKEN_NODE_FRONTIER(ctx)
  init_precedence_stack(&prec_stack, ctx->PREC_ALLOC_SIZE);
  main_reduction_list = (reduction_list*) malloc(sizeof(reduction_list));
  init_reduction_list(main_reduction_list);
  temp_reduction_list = (reduction_list*) malloc(sizeof(reduction_list));
  init_reduction_list(temp_reduction_list);

  /* Done initializing. Start the parsing process. */
  CHRONO_GETTIME(&chrono.timer_s)
    while (current_list_pos != NULL) {
      DEBUG_PRINT("NEW ITERATION ===============================================\n")
      DEBUG_PRINT("Current token: %s, current_list_pos: %p, TERMINATOR: %d \n",
        ctx->gr_token_name[token_value(current_list_pos->token)], current_list_pos, TERMINATOR)
      PRINT_PRECEDENCE_STACK(&prec_stack)
      /* If next token is nonterminal just move on. */
      if (!is_terminal(current_list_pos->token)) {
        CHRONO_GETTIME(&chrono.nonterm_timer_s)
        DEBUG_PRINT("Found nonterminal: %s\n",
          ctx->gr_token_name[token_value(current_list_pos->token)])
        /* Get next token. */
        get_next_token(&current_list_pos, &prev_list_pos, list_end, c_next, &TERMINATOR, ctx->gr_token_name);
        CHRONO_TIMER(&chrono.nonterm_timer_s, &chrono.nonterm_timer_e, &chrono.nonterm_timer_t)
        continue;
      }
      CHRONO_GETTIME(&chrono.prec_timer_s)
      /* Set precedence relationship between last stack terminal token and new token. */
      DEBUG_PRINT("Setting precedence relation.\n")
      prec = set_precedence(current_list_pos, &prec_stack, c_prev, list_end, ctx);
      CHRONO_TIMER(&chrono.prec_timer_s, &chrono.prec_timer_e, &chrono.prec_timer_t)
      /* Do something based on prec. */
      if (prec == EQ || prec == LT) {
        CHRONO_GETTIME(&chrono.stacking_timer_s)
        DEBUG_PRINT("Prec = '%s'\n", prec_name[prec])
        /* Manage stacking. */
        if (TERMINATOR) {
          return_wip(result, &chrono, current_list_pos, &prec_stack, main_reduction_list, temp_reduction_list, &stack, ctx);
          return result;
        }
        /* Push token_node on top of prec_stack. */
        if (prec == LT) {
          if (prev_list_pos != NULL && !is_terminal(prev_list_pos->token)) {
            DEBUG_PRINT("Before get_last_terminal.\n")
            prev_list_pos = get_last_terminal(&prec_stack, c_prev, current_list_pos, list_end);
            DEBUG_PRINT("After get_last_terminal.\n")
          }
          push_precedence_node_on_stack(&prec_stack, prev_list_pos, ctx->PREC_REALLOC_SIZE);
        }
        /* Get next token. */
        get_next_token(&current_list_pos, &prev_list_pos, list_end, c_next, &TERMINATOR, ctx->gr_token_name);
        CHRONO_TIMER(&chrono.stacking_timer_s, &chrono.stacking_timer_e, &chrono.stacking_timer_t)
      } else if (prec == GT) {
        CHRONO_GETTIME(&chrono.reduction_timer_s)
        DEBUG_PRINT("Prec = '>'\n")
        PRINT_PRECEDENCE_STACK(&prec_stack)
        if (!TERMINATOR && prec_stack.tos == 0) {
          /* Get next token. */
          get_next_token(&current_list_pos, &prev_list_pos, list_end, c_next, &TERMINATOR, ctx->gr_token_name);
          CHRONO_TIMER(&chrono.reduction_timer_s, &chrono.reduction_timer_e, &chrono.reduction_timer_t)
          continue;
        }
        if (TERMINATOR && prec_stack.tos == 0) {
          return_wip(result, &chrono, current_list_pos, &prec_stack, main_reduction_list, temp_reduction_list, &stack, ctx);
          return result;
        }
        /* node is the offset of the root of the reduction tree. */
        node = ctx->reduction_tree[0];
        prev_list_pos = pop_precedence_node_from_stack(&prec_stack);
        if (prev_list_pos == NULL) {
          list_itr = list_begin;
        } else {
          list_itr = prev_list_pos->next;
        }
        /* Set the first element of the reduction list to the root. */
        append_position_on_reduction_list(main_reduction_list, node);
        REDUCTION_ERROR = 0;
        DEBUG_PRINT("Begin handle identification, list_itr %p, %s\n",
          list_itr, ctx->gr_token_name[token_value(list_itr->token)])
        /* Begin handle identification. */
        CHRONO_GETTIME(&chrono.backtrack_timer_s)
        while (!REDUCTION_ERROR && list_itr != NULL && list_itr != current_list_pos && list_itr != list_end) {
          DEBUG_PRINT("Handle identification, list_itr: %p, %s\n",
            list_itr, ctx->gr_token_name[token_value(list_itr->token)])
          PRINT_REDUCTION_LIST(main_reduction_list)
          /* For each available position in the reduction tree. */
          for (reduction_list_itr = 0; reduction_list_itr < main_reduction_list->tol; ++reduction_list_itr) {
            reduction_step(temp_reduction_list,
              get_reduction_position_at_index(main_reduction_list, reduction_list_itr), list_itr, ctx);
          }
          PRINT_REDUCTION_LIST(temp_reduction_list)
          swap_reduction_lists(&temp_reduction_list, &main_reduction_list);
          DEBUG_PRINT("Finished building reduction_list.\n")
          DEBUG_PRINT("reduction_list-> ")
          PRINT_REDUCTION_LIST(main_reduction_list)
          DEBUG_PRINT("temp_reduction_list-> ")
          PRINT_REDUCTION_LIST(temp_reduction_list)
          /* If there is at least one available position in the reduction tree after having considered current token, go on. */
          if (main_reduction_list->tol <= 0) {
            REDUCTION_ERROR = 1;
          }
          get_next_reduction_token(&list_itr);
          DEBUG_PRINT("Finished handle identification iteration.\n")
        }
        DEBUG_PRINT("Finished handle identification phase.\n") 
        CHRONO_TIMER(&chrono.backtrack_timer_s, &chrono.backtrack_timer_e, &chrono.backtrack_timer_t)
        PRINT_TOKEN_NODE_FRONTIER(ctx)
        /* Finished handle identification. */
        if (!REDUCTION_ERROR && ctx->reduction_tree[get_reduction_position_at_index(main_reduction_list, 0)] == GRAMMAR_SIZE) {
          DEBUG_PRINT("Not in reducible position.\n")
          REDUCTION_ERROR = 1;
        }
        DEBUG_PRINT("Finished handle identification: REDUCTION_ERROR %d\n", REDUCTION_ERROR)
        if (!REDUCTION_ERROR) {
          CHRONO_GETTIME(&chrono.token_timer_s)
          call_semantics(&chrono, main_reduction_list, &prec_stack, prev_list_pos, &stack, ctx);
          PRINT_TOKEN_NODE_FRONTIER(ctx)
          CHRONO_TIMER(&chrono.token_timer_s, &chrono.token_timer_e, &chrono.token_timer_t)
        } else {
          return_not_recognized(result, &chrono, current_list_pos, &prec_stack, main_reduction_list, temp_reduction_list, &stack, ctx);
          return result;
        }
        CHRONO_GETTIME(&chrono.term_timer_s)
        main_reduction_list->tol = 0;
        if (c_prev->token == TERM && ctx->token_list->next == NULL && current_list_pos->token == TERM &&
            !is_terminal(ctx->token_list->token) && rewrite_to_axiom(ctx->token_list->token, ctx)) {
          perform_rewrite(c_prev, ctx->token_list->token, S, &stack, ctx);
          return_success(result, &chrono, current_list_pos, &prec_stack, main_reduction_list, temp_reduction_list, &stack, ctx);
          return result;
        }
        CHRONO_TIMER(&chrono.reduction_timer_s, &chrono.reduction_timer_e, &chrono.reduction_timer_t)
        CHRONO_TIMER(&chrono.term_timer_s, &chrono.term_timer_e, &chrono.term_timer_t)
      } else {
        /* We should not get here. */
        return_error(result, &chrono, current_list_pos, &prec_stack, main_reduction_list, temp_reduction_list, &stack, ctx);
        return result;
      }
    }
  return_error(result, &chrono, current_list_pos, &prec_stack, main_reduction_list, temp_reduction_list, &stack, ctx);
  return result;
}

inline uint32_t get_son_with(const uint16_t *tree, uint32_t offset, gr_token label)
{
  uint32_t itr;

  for (itr = offset + 2; itr < offset + tree[offset + 1] + 2; itr += 2) {
    if (tree[itr] == token_value(label)) {
      return tree[itr + 1];
    }
  }
  return 0;
}

